package com.rui.shangXueTang.kruskal.prim;

import java.util.Arrays;

/**
 * @author : [锐神NO.3]
 * @version : [v1.0]
 * @className : MinTree
 * @createTime : [2022/2/19 20:09]
 * @description : [描述该类的功能]
 */

@SuppressWarnings("all")
public class MinTree {

    public void createGraph(MGraph graph, int vrexs, char[] data, int[][] weight){
        for(int i = 0 ; i < vrexs ; i++){
            graph.data[i] = data[i];
            for(int j = 0 ; j < vrexs ; j++){
                graph.weight[i][j] = weight[i][j];
            }
        }
    }

    /**
     * 查看邻接举证
     * @param graph 要查看的矩阵
     */
    public void showGraph(MGraph graph){
        for(int[] data : graph.weight){
            System.out.println(Arrays.toString(data));
        }
    }

    public void prim(MGraph graph, int v){
        //标记被访问过的，0表示没有被访问过，1表示访问过
        int[] visied = new int[graph.verxs];
        visied[v] = 1;

        int x = -1;
        int y = -1;

        int minWeight = 10000;
        for(int i = 1 ; i < graph.verxs ; i++){
            //被访问过的
            for(int j = 0 ; j < graph.verxs ; j++){
                //没有被访问过
                for(int k = 0 ; k < graph.verxs ; k++){
                    if(visied[j] == 1 && visied[k] == 0 && graph.weight[j][k] < minWeight){
                        minWeight = graph.weight[j][k];
                        x = j;
                        y = k;
                    }
                }
            }
            System.out.println(graph.data[x] + "--" + graph.data[y] + ":" + minWeight);
            visied[y] = 1;
            minWeight = 10000;
        }
    }
}
